#include <iostream>
#include <vector>
#include "lib/list.h"
using namespace std;

int findKthToTail(ListNode** phead, int k) {
  if (phead == nullptr || *phead == nullptr || k == 0) {
    return 0;
  }
  auto fast_node = *phead;
  auto slow_node = *phead;
  for (auto i = 0; i < k - 1; ++i) {
    if (fast_node->next != nullptr) {
      fast_node = fast_node->next;
    } else {
      return 0;
    }
  }
  while (fast_node->next != nullptr) {
    fast_node = fast_node->next;
    slow_node = slow_node->next;
  }
  return slow_node->value;
}

int findInterNode(ListNode** phead) {
  if (phead == nullptr || *phead == nullptr) {
    return 0;
  }
  auto slow_node = *phead;
  auto fast_node = *phead;
  while (fast_node->next && fast_node->next->next) {
    fast_node = fast_node->next->next;
    slow_node = slow_node->next;
  }
  return slow_node->value;
}

int main() {
  vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8};
  ListNode* phead = CreateList(vec);
  int ret = findKthToTail(&phead, 5);
  cout << "findKthToTail: " << ret << endl;

  vector<int> vec1 = {1, 2, 3, 4, 5, 6, 7, 8};
  ListNode* phead1 = CreateList(vec1);
  int ret1 = findInterNode(&phead1);
  cout << "findInterNode: " << ret1 << endl;

  vector<int> vec2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  ListNode* phead2 = CreateList(vec2);
  int ret2 = findInterNode(&phead2);
  cout << "findInterNode: " << ret2 << endl;

  return 0;
}
